#include "heap.h"
#include "logger.h"
#include <string.h>
PriorityQueue Initialize(
    int Capacity,
    HeapIfNull _heap_if_null,
    HeapCompare _heap_compare,
    HeapCopy _heap_copy,
    HeapGenMinEle _gen_min_ele,
    HeapReleaseMinEle _release_min_ele,
    HeapPrintEle _print_ele)
{
    if (!_heap_compare || !_heap_copy || !_gen_min_ele || !_print_ele || !_release_min_ele || !_heap_if_null)
        FatalError("Invalid arg");

    if (Capacity < MinPQSize)
        FatalError("Capacity too small");

    PriorityQueue H = malloc(sizeof(*H));
    if (!H)
        FatalError("Out of space");
    //Capacity + 1是为了给index预留空间
    H->ElementList = malloc((Capacity + 1) * sizeof(*H->ElementList));
    H->Capacity = Capacity;
    H->Size = 0;
    H->_heap_if_null = _heap_if_null;
    H->_heap_compare = _heap_compare;
    H->_heap_copy = _heap_copy;
    H->_gen_min_ele = _gen_min_ele;
    H->_print_ele = _print_ele;
    H->_release_min_ele = _release_min_ele;
    H->_gen_min_ele(&(H->ElementList[0]), MinData);
_success:
    goto _exit;
_error:
    Destory(H);
    H = NULL;
    goto _exit;
_exit:
    return H;
}

void Destory(PriorityQueue H)
{
    int i = 0;
    H->_release_min_ele(H->ElementList[0]);
    if (H)
    {
        MakeEmpty(H);
        free(H);
    }
}

void MakeEmpty(PriorityQueue H)
{
    H->Size = 0;
}

void Insert(ElementType X, PriorityQueue H)
{
    int i = 0;
    if (IsFull(H))
        FatalError("Heap is full");
    if (H->_heap_if_null(X))
        FatalError("Invalid arg");
    if (H->_heap_compare(X, H->ElementList[0]) <= 0)
        FatalError("X is too small");

    //预备插入的位置为heap中的后一个位置，然后进行上滤比较父节点和他的大小，找到可以交换的数据
    //最终当i=1时, 位于0位置的值始终小于1，因此可以跳出循环
    for (i = ++H->Size; H->_heap_compare(H->ElementList[i / 2], X) > 0; i /= 2)
        H->_heap_copy(&(H->ElementList[i]), H->ElementList[i / 2]);
    H->_heap_copy(&(H->ElementList[i]), X);
}

ElementType DeleteMin(PriorityQueue H)
{
    int i = 0, Child = 0;
    if (IsEmpty(H))
        FatalError("Heap is empty");
    ElementType MinElement = H->ElementList[1];
    ElementType LastElement = H->ElementList[H->Size--];
    //当i有右子树或者没有右子树
    for (i = 1; i * 2 <= H->Size; i = Child)
    {
        //当Child=H->Size时，则只有左子树，否则有右子树
        //找到数值较小的子树节点
        Child = i * 2;
        if (Child != H->Size && H->_heap_compare(H->ElementList[Child], H->ElementList[Child + 1]) > 0)
            Child++;

        //测试是否应该将最后一个元素安排在这里
        if (H->_heap_compare(LastElement, H->ElementList[Child]) > 0)
            H->_heap_copy(&(H->ElementList[i]), H->ElementList[Child]);
        else
            break;
    }
    H->_heap_copy(&(H->ElementList[i]), LastElement);

    return MinElement;
}

ElementType FindMin(PriorityQueue H)
{
    if (IsEmpty(H))
        FatalError("Heap is empty");
    return H->ElementList[1];
}

int IsEmpty(PriorityQueue H)
{
    return H->Size == 0;
}
int IsFull(PriorityQueue H)
{
    return H->Capacity == H->Size;
}

static void Print(PriorityQueue H, int index)
{
    int TabNum = index / 2;
    int i = 0;
    for (i = 0; i < TabNum; i++)
    {
        printf(" ");
    }
    if (index % 2)
        printf("左");
    else
        printf("右");
    H->_print_ele((void *)H->ElementList[index]);
    if (2 * index <= H->Size)
        Print(H, 2 * index);
    if (2 * index + 1 <= H->Size)
        Print(H, 2 * index + 1);
}

void PrintTree(PriorityQueue H)
{
    int i = 0;
    if (IsEmpty(H))
        FatalError("Heap is empty");
    Print(H, 1);
}